120. 三角形最小路径和

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/triangle/

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

分析

首先要弄清楚什么叫相邻节点。也就是三角形里面的列表，索引相等或者加一，为相邻坐标。

本题有一个非常明显的递推关系，就是第n层的最短路径，依赖于第n-1层，以上面的例子来说，到了最后一层的1，它的最短路径，依赖于上一层6、5的最短路径。然后取其中较小的连成一条路径，作为自己的最短路径。

意思也就是说当我们到达了第n层的某个数，只要它n-1层的两个点都已经是最短路径了，那么我只需要选择其中较小者，作为当前的最短路径即可。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:

    def __init__(self):
        self.dp = None

    def minimumTotal(self, triangle) -> int:
        if len(triangle) == 0:
            return 0
        self.dp = [[0] * len(triangle[i]) for i in range(len(triangle))]
        self.dp[0][0] = triangle[0][0]
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i])):
                # 判断边界的情况
                if j == 0:
                    # 没有j-1的情况
                    pre_num = self.dp[i - 1][j]
                elif j == len(triangle[i]) - 1:
                    # 没有j的情况
                    pre_num = self.dp[i - 1][j - 1]
                else:
                    pre_num = min(self.dp[i - 1][j], self.dp[i - 1][j - 1])
                self.dp[i][j] = pre_num + triangle[i][j]

        return min(self.dp[-1])

进阶

本题还有一个进阶的要求：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

然后我们思考，本题为什么可以使用O(n)的空间解决，其实稍作思考也就知道了，n层结果，依赖于n-1层，而和更前面的层没有关系，所以我们并不用把所有层的记录都记下来，因而可以使用O(n)的空间复杂度解决。

那么将n层的结果和n-1层写在一起会有问题嘛？

当然会有，n层依赖于n-1层的结果,
比如n层第i个位置，实际上依赖于n-1层的第i-1个位置和第i个位置，所以如果我们这样做，那么在计算完第i个位置后，我们会覆盖掉这个位置，当n层走到第i+1的时候，找n-1层的第i个位置的时候，发现被覆盖了！
所以，我们倒过来走就好了呀！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:

    def __init__(self):
        self.dp = None

    def minimumTotal(self, triangle) -> int:
        if len(triangle) == 0:
            return 0
        self.dp = [0] * len(triangle[-1])
        self.dp[0] = triangle[0][0]
        for i in range(1, len(triangle)):
            for j in range(len(triangle[i]) - 1, -1, -1):
                # 判断边界的情况
                if j == 0:
                    # 没有j-1的情况
                    pre_num = self.dp[j]
                elif j == len(triangle[i]) - 1:
                    # 没有j的情况
                    pre_num = self.dp[j - 1]
                else:
                    pre_num = min(self.dp[j], self.dp[j - 1])
                self.dp[j] = pre_num + triangle[i][j]
        return min(self.dp)

Alt text

可以看到，效果还是很可观的，一下子内存消耗就较少了！